home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / c_toolbx.arc / BT_INS.C < prev    next >
Encoding:
C/C++ Source or Header  |  1988-03-30  |  3.8 KB  |  122 lines
  1. /*  bt_ins.c - insert function */
  2. #include   "stdio.h"
  3. #include   "btree.h"
  4. #include   "bt_macro.h"
  5.  
  6. extern    IX_DESC    *pci ;    /* refers to index descriptor */
  7.                 /* for current function call  */
  8. extern     BLOCK     spare_block ;    /* scratch block for splits and */
  9.                 /* compressing */
  10. extern     int  split_size ;    /* treshold for splitting the block */
  11.  
  12. int  insert_ix(pe,pix)            /* find first entry with key */
  13.   ENTRY *pe ;                /* points to key to be matched */
  14.                     /* store the rec. loc. here */
  15.   IX_DESC  *pix ;            /* points to index descriptor */
  16.   {                    /* returns success=1, failure=0 */
  17.      int ret ;
  18.      BLOCK b ;
  19.  
  20.      pci = pix ;
  21.      ret = ins_level(0,pe,&b) ;     /* insert entry at leafe level */
  22.  
  23.      if( ret == IX_OK )         /* if the insertion worked */
  24.     next_ix(0,&b) ;         /* move past entry inserted */
  25.  
  26.      return ( ret ) ;            /* return success / failure */
  27.   }
  28.  
  29.  
  30. int  ins_level(l,pe,pb)         /* insert an entry at  */
  31.   int l ;                /* this level */
  32.   ENTRY *pe ;                /* points to entry */
  33.   BLOCK *pb ;
  34.   {
  35.      RECPOS   r ;
  36.      int   ret ;
  37.  
  38.      if( l >= pci->dx.nl )        /* do we need a new level ? */
  39.     return( IX_FAIL ) ;        /* yes - overflow */
  40.  
  41.      retrieve_block(l,CB(l),pb,CURR) ;
  42.                     /* does it fit into the block ? */
  43.      if( (pb->bend + ENT_SIZE(pe)) <= split_size )
  44.     {  ins_block(pb,pe,CO(l)) ;    /* yes - put entry into block */
  45.        update_block(pb) ;
  46.        ret = IX_OK ;
  47.     }
  48.      else ret = split(l,pe,pb) ;    /* no - split the block  */
  49.  
  50.      return( ret ) ;
  51.   }
  52.  
  53. int  split(l,pe,pb)            /* split a block into two */
  54.   int    l ;
  55.   ENTRY *pe ;
  56.   BLOCK *pb ;
  57.   {
  58.      int   half, ins_pos, last, ret ;
  59.      BLOCK *pbb ;
  60.      ENTRY e ;
  61.  
  62.      ins_pos = CO(l) ;            /* remember where insert was */
  63.  
  64.      if( (l+1) >= pci->dx.nl )        /* check for top level */
  65.     return( IX_FAIL ) ;        /* (can't split top level block) */
  66.  
  67.                     /* allocate a big block */
  68.      pbb = (BLOCK *) calloc(sizeof(BLOCK)+sizeof(ENTRY),1) ;
  69.      if( pbb == NULL )            /* did allocation fail ? */
  70.     return( IX_FAIL ) ;        /* yes - exit */
  71.  
  72.                     /* do insert in big block */
  73.      pbb->bend = 0 ;
  74.      combine(pb,pbb) ;            /* copy contents of old buffer */
  75.      ins_block(pbb,pe,CO(l)) ;        /* insert new entry */
  76.  
  77.                     /* now find where to split */
  78.                     /* no more than 1/2 in left block */
  79.      last = scan_blk(pbb,pbb->bend/2) ; /* start of last entry */
  80.                     /* in left half o bib block */
  81.      half = next_entry(pbb,last) ;    /* end of left half */
  82.                 /* allocate disk space for left block */
  83.      if( get_block(l,pbb) == IX_FAIL )    /* check for failure */
  84.     {  free(pbb) ;
  85.        return( IX_FAIL ) ;
  86.     }
  87.                 /* make an entry for the new block */
  88.                     /* on the upper level */
  89.      copy_entry(&e,ENT_ADR(pbb,last) ) ;
  90.      e.rptr = pbb->brec ;        /* point entry to left block */
  91.  
  92.      ret = ins_level(l+1,&e,pb) ;    /* inserting new index entry */
  93.                     /* for left block at higher level */
  94.                     /* ( this makes the l+1 position  */
  95.                     /* point to the left block )      */
  96.      if( ret != IX_OK )         /* check for higher level failure */
  97.     {  free(pbb)  ;         /* yes - free big block area      */
  98.        put_free(pbb) ;        /*     free new index block      */
  99.        return( ret ) ;        /*     return failure code      */
  100.     }
  101.  
  102.                     /* use pb for right block   */
  103.      mover(ENT_ADR(pb,0),ENT_ADR(pbb,half),pbb->bend-half) ;
  104.      pb->bend = pbb->bend - half ;
  105.      pb->brec = CB(l) ;         /* restore blosk's location */
  106.      pb->lvl  = l ;            /* and it's level */
  107.      update_block(pb) ;         /* and update left block */
  108.  
  109.                     /* adjust current position */
  110.      if( ins_pos >= half )        /* is curr entry in left or right */
  111.     {  CO(l) = CO(l) - half ;    /* right - and adjust offset */
  112.        next_ix(l+1,pb) ;        /*       upper level pos. */
  113.     }
  114.      else CB(l) = e.rptr ;        /* left - make left block current */
  115.      free(pbb) ;            /* free the big scratch block */
  116.  
  117.      return( ret ) ;
  118.   }
  119.  
  120.  
  121.  
  122.